import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-03
 * Time: 23:55
 */
class Solution {
    public void reverse(int[] arr, int left,int right){
        while(left<right){
            int temp=arr[left];
            arr[left]=arr[right];
            arr[right]=temp;
            left++;
            right--;
        }
    }
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        List<List<Integer>> ret=new ArrayList<>();
        int row=grid.length;
        int col=grid[0].length;
        int length=row*col;
        //展开为一维数组
        int index=0;
        int[] arr=new int[length];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                arr[index++]=grid[i][j];
            }
        }
        //迁移k次相当于循环右移k次
        k%=length;
        int mid=length-k;
        reverse(arr,0,mid-1);
        reverse(arr,mid,length-1);
        reverse(arr,0,length-1);
        for(int i=0;i<row;i++){
            List<Integer> list=new ArrayList<>();
            for(int j=0;j<col;j++){
                list.add(arr[i*col+j]);
            }
            ret.add(list);
        }
        return ret;
    }
}
